Năm 1953, Nam đến phục vụ trong Sư đoàn Bộ binh 29 đóng tại đảo Cheju với cấp bậc Đại úy quân đội Hàn Quốc. Tại đây, Nam gặp Choe Hong Hui,[1], khi đó là Tư lệnh Sư đoàn với cấp bậc Thiếu tướng, và tham gia thành lập võ đường Oh Do Kwan để huấn luyện võ thuật cho binh sĩ trong sư đoàn. Nam nhanh chóng trở thành nhân vật thứ hai đứng sau Choe trong lĩnh vực hệ thống các kỹ thuật mới và đóng vai trò chủ chốt trong việc phát triển taekwondo. Ông được mệnh danh là "cánh tay phải của Choe Hong Hui", như trong một bản tiểu sử về ông được công bố chính thức sau đó.[8]. Năm 1954, tham gia một buổi biểu diễn võ thuật của các binh sĩ Hàn Quốc trước sự chứng kiến của Tổng thống Lý Thừa Vãn, Nam, khi đó mang đai đen nhị đẳng, đã biểu diễn công phá vỡ một chồng gạch gồm 13 viên ngói chỉ bằng một cú đấm từ trên giáng xuống. Tổng thống Lý Thừa Vãn rất ấn tượng trước màn trình diễn đó và đã hạ lệnh cho toàn thể binh sĩ phải luyện tập võ thuật.[3][6][9][10]

Tháng 3 năm 1959, Nam Tae Hui trở thành một thành viên trong nhóm những võ sư và võ sinh taekwondo đi lưu diễn trên thế giới, họ tổ chức biểu diễn taekwondo ở Nam Việt Nam và Đài Loan.[1] Lúc đó, ông được cử làm Chủ tịch Liên đoàn Taekwondo châu Á và là một trong những sáng lập viên của Hiệp hội Taekwondo Hàn Quốc (KTA).[8] Năm 1962, Nam trở thành Huấn luyện viên trưởng của môn taekwondo trong quân đội Việt Nam Cộng hòa và được gọi là Người cha của Taekwondo ở Việt Nam.[1] Ông cũng là người tham gia xây dựng các bài quyền của môn phái Chang Hon như Hwa-Rang, Chung-Mu, và UI-Ji.[1]

Năm 1966, khi Liên đoàn Taekwondo Quốc tế được thành lập, ông được cử vào chức vụ Phó chủ tịch, đồng thời kiêm nhiệm chức vụ Chủ tịch Liên đoàn Taekwondo Á châu (Asian Taekwon-Do Federation - ATF)